package com.mdnote.practice.devide_and_rule;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/15
 * @description 子集
 */
public class LeetCode78 {

    public static void main(String[] args) {
        LeetCode78 leetCode78 = new LeetCode78();
        leetCode78.subsets(new int[]{1, 2, 3});
    }

    public List<List<Integer>> subsets(int[] nums) {
        if (nums.length == 0) {
            return new ArrayList<>();
        }
        // recursion
//        List<List<Integer>> list = new ArrayList<>();
//        recursion(1, new ArrayList<Integer>(),  nums, list);
//        list.forEach(System.out::println);
        // for loop

        List<List<Integer>> list = forLoop(nums);
        list.forEach(System.out::println);
        return list;
    }

    private List<List<Integer>> forLoop(int[] nums) {

        // 这里有一个思路
        List<List<Integer>> resList = new ArrayList<>();
        // 添加第一种可能
        resList.add(new ArrayList<>());
        for (int i = 0; i < nums.length; i++) {
            // 一定要吧size拿出来
            int size = resList.size();
            for (int j = 0; j < size; j++) {
                List<Integer> tempNode = new ArrayList<>(resList.get(j));
                tempNode.add(nums[i]);
                resList.add(tempNode);
            }
        }

        return resList;
    }

    private void recursion(int level, List<Integer> res,  int[] nums, List<List<Integer>> list) {

        // Terminator
        if (level > nums.length) {
            list.add(new ArrayList<>(res));
            return;
        }

        // process current logic & decide big question
        // 不添加当前字符
        recursion(level + 1, res, nums, list);

        // 添加当前字符到集合
        res.add(nums[level - 1]);
        recursion(level + 1, res, nums, list);
        // restore current data
        res.remove(Integer.valueOf(nums[level - 1]));

    }
}
